﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
/*
==========================================================
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
==========================================================
*/


//法一，合并两个有序数组，然后直接取中位数，时间复杂度高，但较简洁易懂


//法二，二分，根据中位数左边和右边元素个数相等的性质，
//求一条分割线，保证分隔线左边恒小于等于右边，则中位数一定与分割线处的几个数有关，注意奇偶



//第一次编写记录:被极端情况暴打q_q
//double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) 
//{
//	//保证两个数组第一个长度小于等于第二个，方便后续操作
//	if (nums2Size < nums1Size)
//	{
		//int* tmp = nums1;
		//nums1 = nums2;
		//nums2 = tmp;

		//int tmp_size = nums1Size;
		//nums1Size = nums2Size;
		//nums2Size = tmp_size;
//	}
//	int left = 0;
//	int right = nums1Size;
//	int i = 0;
//	int j = 0;
//	//由于nums1较小，有两种极端情况，nums1的元素全在分割线右边，nums1的元素全在分割线左边，需注意
//	while (left <= right)
//	{
//		int mid = left + (right - left) / 2;
//		i = mid;
//		j = (nums1Size + nums2Size+1) / 2 - i;
//		if ( i>0 &&nums1[i - 1] > nums2[j])//分割线太右边
//		{
//			right = mid-1;
//		}
//		else if (i<nums1Size &&nums2[j - 1] > nums1[i])//分割线太左边
//		{
//			left = mid + 1;
//		}
//		else		//找到分割线
//		{
//			break;
//		}
//	}
//	int left_max = 0;//分割线左边最大值
//	int right_min = 0;//分割线右边最小值
//	//注意考虑极端情况，难点
//	if (i == 0)
//	{
//		left_max = nums2[j - 1];
//	}
//	else if (j == 0)
//	{
//		left_max = nums1[i - 1];
//	}
//	else
//	{
//		left_max = nums1[i - 1] > nums2[j - 1] ? nums1[i - 1] : nums2[j - 1];
//	}
//	//总长度为奇数
//	if((nums1Size+nums2Size) % 2 == 1)
//	{
//		return left_max;
//	}
//	if (i == nums1Size)
//	{
//		right_min = nums2[j];
//	}
//	else if (j == nums2Size)
//	{
//		right_min = nums1[i];
//	}
//	else
//	{
//		right_min = nums1[i] > nums2[j ] ? nums2[j] : nums1[i];
//	}
//	//总长度为偶数
//	if ((nums1Size + nums2Size) % 2 == 0)
//	{
//		return (left_max + right_min) / 2.0;
//	}
//}




//法三，最小k算法，中位数即找到最小的第n+m/2个数

int Find_k(int* nums1, int nums1Size, int* nums2, int nums2Size,int k)
{
	if (nums1Size <= 0)
	{
		return nums2[k - 1];
	}
	else if (nums2Size <= 0)
	{
		return nums1[k - 1];
	}
	else if (k == 1)//递归终点
	{
		return nums1[0] > nums2[0] ? nums2[0] : nums1[0];
	}
	int i = (k / 2 - 1)> (nums1Size-1)? (nums1Size - 1): (k / 2 - 1);//防止i过大超过数组空间
	int j = k-i-2;
	int ret = 0;

	if (nums1[i] < nums2[j])
	{
		//去除nums1[i]前面的部分，前面的部分肯定是 小于 第k小的数的
		ret= Find_k(nums1 + i + 1, nums1Size - i - 1, nums2, nums2Size, k - i - 1);//递归，假设去除n个数，则再求第k-n小的数
	}
	else
	{
		ret=Find_k(nums1, nums1Size,nums2+j+1, nums2Size - j - 1,k-j-1);
	}
	return ret;
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
	if (nums1Size > nums2Size)
	{
		int* tmp = nums1;
		nums1 = nums2;
		nums2 = tmp;

		int tmp_size = nums1Size;
		nums1Size = nums2Size;
		nums2Size = tmp_size;
	}
	if ((nums1Size + nums2Size) % 2 == 1)//找第(nums1Size + nums2Size+1)/2个元素
	{
		int k = (nums1Size + nums2Size + 1) / 2;
		return (double)Find_k(nums1, nums1Size, nums2, nums2Size, k);
	}
	else//找第(nums1Size + nums2Size+1)/2个元素和第(nums1Size + nums2Size+1)/2+1个元素
	{
		int left_k = (nums1Size + nums2Size + 1) / 2;
		int right_k = (nums1Size + nums2Size + 1) / 2 + 1;
		return (Find_k(nums1, nums1Size, nums2, nums2Size, left_k) \
			+Find_k(nums1, nums1Size, nums2, nums2Size, right_k)) / 2.0;
	}
}

int main()
{
	int arr1[2] = {1,3};
	int arr2[1] = { 2};
	printf("%lf",findMedianSortedArrays(arr1, 2, arr2, 1));
	return 0;
}

